﻿using System;
using System.Runtime.CompilerServices;

namespace fastCSharp
{
    /// <summary>
    /// 数组模拟最小堆
    /// </summary>
    /// <typeparam name="keyType">关键字类型</typeparam>
    /// <typeparam name="valueType">数据类型</typeparam>
    public sealed class arrayHeap<keyType, valueType> where keyType : IComparable<keyType>
    {
        /// <summary>
        /// 默认数组长度
        /// </summary>
        private const int defaultArrayLength = 256;
        /// <summary>
        /// 数据数组
        /// </summary>
        private keyValue<keyType, valueType>[] array;
        /// <summary>
        /// 最小堆索引
        /// </summary>
        private int[] heap;
        /// <summary>
        /// 数据数量
        /// </summary>
        public int Count { get; private set; }
        /// <summary>
        /// 根节点索引
        /// </summary>
        private int bootIndex;
        /// <summary>
        /// 数组模拟最小堆
        /// </summary>
        public arrayHeap()
        {
            array = new keyValue<keyType, valueType>[defaultArrayLength];
            heap = new int[defaultArrayLength];
        }
        /// <summary>
        /// 添加数据
        /// </summary>
        /// <param name="key">关键字</param>
        /// <param name="value">数据值</param>
        [MethodImpl((MethodImplOptions)fastCSharp.pub.MethodImplOptionsAggressiveInlining)]
        public void Add(keyType key, valueType value)
        {
            Push(key, value);
        }
        /// <summary>
        /// 添加数据
        /// </summary>
        /// <param name="key">关键字</param>
        /// <param name="value">数据值</param>
        public unsafe void Push(keyType key, valueType value)
        {
            int index = Count;
            if (index == array.Length)
            {
                keyValue<keyType, valueType>[] newArray = new keyValue<keyType, valueType>[index << 1];
                array.CopyTo(newArray, 0);
                int[] newHeap = new int[index << 1];
                heap.CopyTo(newHeap, 0);
                heap = newHeap;
                array = newArray;
            }
            array[index].Set(key, value);
            if (index == 0) heap[bootIndex = 1] = 0;
            else
            {
                fixed (int* heapFixed = heap)
                {
                    if ((index >> 1) == bootIndex)
                    {
                        heapFixed[index] = heapFixed[bootIndex];
                        bootIndex = index;
                    }
                    if ((index & 1) == 0 || key.CompareTo(array[index ^ 1].Key) < 0)
                    {
                        int heapIndex = index | 1, xor = 1;
                        heapFixed[heapIndex] = index;
                        while (xor != bootIndex)
                        {
                            int cmpHeapIndex = heapIndex ^ (xor <<= 1);
                            if ((heapIndex & xor) == 0 || key.CompareTo(array[heapFixed[cmpHeapIndex]].Key) < 0)
                            {
                                heapFixed[heapIndex = (int)(((uint)heapIndex + (uint)cmpHeapIndex) >> 1)] = index;
                            }
                            else break;
                        }
                    }
                }
            }
            ++Count;
        }
        /// <summary>
        /// 弹出堆顶数据
        /// </summary>
        /// <returns>堆顶数据</returns>
        public unsafe keyValue<keyType, valueType> Pop()
        {
            if (Count == 0) throw new IndexOutOfRangeException();
            int index = heap[bootIndex];
            keyValue<keyType, valueType> value = array[index];
            removeTop(index);
            return value;
        }
        /// <summary>
        /// 删除堆顶数据
        /// </summary>
        /// <param name="index">堆顶数据索引位置</param>
        private unsafe void removeTop(int index)
        {
            if (--Count == 0) array[index].Set(default(keyType), default(valueType));
            else
            {
                fixed (int* heapFixed = heap)
                {
                    if (index != Count)
                    {
                        keyType key = (array[index] = array[Count]).Key, cmpKey = array[index ^ 1].Key;
                        int heapIndex = index | 1;
                        if (key.CompareTo(cmpKey) > 0)
                        {
                            index ^= 1;
                            key = cmpKey;
                            heapFixed[heapIndex] = index;
                        }
                        for (int xor = 1; xor != bootIndex; heapFixed[heapIndex] = index)
                        {
                            int cmpHeapIndex = heapIndex ^ (xor <<= 1);
                            heapIndex = (int)(((uint)heapIndex + (uint)cmpHeapIndex) >> 1);
                            if (heapIndex <= Count)
                            {
                                int cmpIndex = heapFixed[cmpHeapIndex];
                                if (key.CompareTo(cmpKey = array[cmpIndex].Key) > 0)
                                {
                                    index = cmpIndex;
                                    key = cmpKey;
                                }
                            }
                        }
                    }
                    array[Count].Set(default(keyType), default(valueType));
                    if (bootIndex == Count) bootIndex >>= 1;
                    else
                    {
                        int heapIndex = (index = Count) | 1;
                        if (heapFixed[heapIndex] == index)
                        {
                            keyType key;
                            int xor = 1;
                            if ((index & 1) == 0)
                            {
                                while ((heapIndex & (xor <<= 1)) == 0) heapIndex += xor >> 1;
                                index = heapFixed[heapIndex ^= xor];
                                xor >>= 1;
                            }
                            else heapFixed[heapIndex] = (index ^= 1);
                            for (key = array[index].Key; xor != bootIndex; heapFixed[heapIndex] = index)
                            {
                                int cmpHeapIndex = heapIndex ^ (xor <<= 1);
                                heapIndex = (int)(((uint)heapIndex + (uint)cmpHeapIndex) >> 1);
                                if (heapFixed[heapIndex] == Count)
                                {
                                    if (cmpHeapIndex < heapIndex)
                                    {
                                        int cmpIndex = heapFixed[cmpHeapIndex];
                                        keyType cmpKey = array[cmpIndex].Key;
                                        if (key.CompareTo(cmpKey) > 0)
                                        {
                                            index = cmpIndex;
                                            key = cmpKey;
                                        }
                                    }
                                }
                                else break;
                            }
                        }
                    }
                }
            }
        }
        /// <summary>
        /// 获取堆顶数据,不弹出
        /// </summary>
        /// <returns>堆顶数据</returns>
        public keyValue<keyType, valueType> Top()
        {
            if (Count == 0) throw new IndexOutOfRangeException();
            return array[heap[bootIndex]];
        }
        /// <summary>
        /// 获取堆顶数据,不弹出
        /// </summary>
        /// <returns>堆顶数据</returns>
        [MethodImpl((MethodImplOptions)fastCSharp.pub.MethodImplOptionsAggressiveInlining)]
        internal keyValue<keyType, valueType> UnsafeTop()
        {
            return array[heap[bootIndex]];
        }
        /// <summary>
        /// 删除堆顶数据
        /// </summary>
        [MethodImpl((MethodImplOptions)fastCSharp.pub.MethodImplOptionsAggressiveInlining)]
        internal void RemoveTop()
        {
            removeTop(heap[bootIndex]);
        }
    }
}
